package com.leetcode.LC_MED;

public class LC560 {
    int num = 0;

    public int subarraySum(int[] nums, int k) {

        for (int i = 0; i < nums.length; i++) {
            dfs(nums, k, i);
        }
        return num;
    }

    private void dfs(int[] nums, int k, int index) {
        if (index >= nums.length) {
            return;
        }
        k -= nums[index];
        if (k == 0) {
            num++;
        }
        dfs(nums, k, index + 1);
    }


    public int subarraySum2(int[] nums, int k) {

        int rs = 0;
        for (int i = 0; i < nums.length; i++) {
            int tmp = 0;
            for (int j = i; j < nums.length; j++) {
                tmp += nums[j];
                if (tmp == k) {
                    rs++;
                }
            }
        }
        return rs;

    }

    public static void main(String[] args) {
        System.out.println(new LC560().subarraySum(new int[]{1, 1, 2, 2, 1, 1, 1}, 2));
    }
}
